This invention is related generally to the field of shared resource arbitration and other methods adaptable and suitable for arbitrating amongst devices competing for access to a shared resource. Specifically the present invention relates to multiple-level bus arbitration techniques and systems.
Bus arbitration techniques are relevant in a wide variety of applications involving shared communication resources. For example, any system employing a set of signal paths shared by more than one device can potentially implement an appropriate bus arbitration algorithm that determines how such devices are given access to the shared signal paths. The design of a bus arbitration technique thus affects greatly the character of signal transmission in such a system. One illustrative system implementing a bus arbitration technique may be a system having different processing, memory, and I/O components linked by a shared set of signal paths and implemented within a single semiconductor device. Another illustrative system may be a computer system having separate subsystems, such as various semiconductor devices, connected through at least one common bus. Yet another illustrative system may be a networked system having a number of different computers connected by a common network interface.
A given bus arbitration technique is typically based on a specific arbitration algorithm. Known arbitration algorithms include fixed-priority algorithms, round-robin algorithms, and most-recently-used (“MRU”) algorithms, which are briefly described below.
Generally, a fixed-priority algorithm provides a fixed order in which devices are granted access to the shared communication resource. For example, in a system having four devices, device 1 through device 4, competing for access to a shared communication resource, a fixed-priority algorithm may provide access to the shared resource in the following order: device 1, followed by device 2, followed by device 3, followed by device 4. That is, when access is to be arbitrated amongst these four particular devices, device 1 is always examined first to determine if it needs the access. If so, access is granted to device 1. Otherwise, device 2 is next examined to determine if it needs the access. If so, access is granted to device 2. Otherwise, device 3 is next examined, and so on. Each time access to the shared communication resource becomes available, it is offered first to device 1, then to device 2, then to device 3, and then to device 4. In this sense, device 1 is always the “starting device ” in a fixed order or priority. Thus, the fixed-priority algorithm is not generally considered fair in that the algorithm always favors device 1 the most, followed by device 2, then device 3, and finally device 4.
A round-robin algorithm generally provides an order in which devices are examined for granting access to the shared communication resource such that the devices take turns at being the starting device in the order. Thus, the order is not fixed. The same system described above having devices 1 through 4 is used as an example. In one arbitration cycle, the devices are examined in the following order: device 1, followed by device 2, followed by device 3, followed by device 4. Here, the starting device is device 1. However, in the next arbitration cycle, the devices are examined in a shifted order: device 2, followed by device 3, followed by device 4, followed by device 1. Here, the starting device is device 2. In this manner, the four devices take turns at being the starting device. Because the round-robin algorithm does not favor one device over another over multiple arbitration cycles, the round-robin algorithm is generally considered more fair than the fixed-priority algorithm in a certain sense.
An MRU algorithm generally provides an order in which devices are examined for granting access to the shared communication resource such that the device that was most recently granted access receives the least consideration in the current arbitration cycle (e.g., is forced to be the last device examined in the order). Again, the system having devices 1 through 4 is used as an example. Assuming in one arbitration cycle, the devices are examined in the following order: device 1, followed by device 2, followed by device 3, followed by device 4, and access to the shared communication resource is granted to device 2, then the order in the subsequent arbitration cycle might be the following: device 3, followed by device 4, followed by device 1, followed by device 2. Since the device that most recently received a grant of access is device 2, the order for the subsequent arbitration cycle places device 2 as the last device in the order to be examined, causing device 2 to receive the least consideration. Thus, the MRU algorithm is also considered more fair in a certain sense than the fixed-priority algorithm.
Current bus arbitration techniques also include bi-level bus arbitration systems, which address the need for providing different priority to different devices in accessing the shared communication resource. In a bi-level bus arbitration system, each device connected to a shared communication resource is assigned to either a high priority group or a low priority group, depending on the urgency with which the device is granted access to the shared communication resource. For example, certain devices handling data, such as audio data, that require more immediate access to the shared communication resource may be assigned to the high priority group. Other devices that can tolerate a longer delay in accessing the shared communication resource may be assigned to the low priority group. Access to the shared communication resource is thus granted based on membership in either the high priority group or low priority group. Generally, devices in the high priority group are provided more immediate access, whereas devices in the low priority group are provided access involving more delay.
While currently available bi-level bus arbitration techniques allow priority access differentiation between two groups of devices, such differentiation is based solely on an assignment of priority. That is, beyond generally providing one group with a higher priority and the other group with a lower priority, there is little distinction between the two groups. Specifically, the same arbitration algorithm is generally applied within each of the two groups. By differentiating between groups of devices on the basis of group priority alone, the currently available bi-level bus arbitration techniques fails to take into account more complex arbitration needs of each of the various priority groups. Consequently, more efficient methods of providing bus arbitration decisions that do take into account such particular needs cannot be achieved using currently available techniques.
There is a need for a bus arbitration technique that is capable of not only providing multiple-level priority arbitration for devices attempting to access a shared communication resource, but also addressing differing arbitration needs between multiple levels of priority.